package com.example.Arithmetic.Arithmetic;

/**
 * 日期：2024/1/1
 * 时间：15:29
 * 描述：最长公共子序列
 * 包含且顺序一样就是子序列
 * 相同值为上一个对角线加1，不同则值为左边和上边中更大的一个
 */
public class LCSubsequence {
    public static void main(String[] args) {
        LCSubsequence code = new LCSubsequence();
        System.out.println(code.longestCommonSubsequence("abcdef", "acef"));
    }

    private int longestCommonSubsequence(String a, String b) {
        int[][] dp = new int[a.length() + 1][b.length() + 1];
        for (int i = 1; i < a.length() + 1; i++) {
            for (int j = 1; j < b.length() + 1; j++) {
                if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Integer.max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        return dp[a.length()][b.length()];
    }
}
